package com.zhengb.algorithmdemo.basic.tree.binarsearchtree;

/**
 * 二叉搜索树相关操作
 *
 * @author zhengbo
 * @date 2020/2/25
 */
public class BstUtils {

    /**
     * 递归方式查找bst元素
     * 时间复杂度O(N) 空间复杂度O(N)
     *
     * @param rootNode
     * @param data
     * @return
     */
    public static BinarySearchTreeNode<Integer> findData(BinarySearchTreeNode<Integer> rootNode, int data) {

        if (rootNode == null) {
            return null;
        }

        if (data < rootNode.getData()) {
            return findData(rootNode.getLeft(), data);
        } else if (data > rootNode.getData()) {
            return findData(rootNode.getRight(), data);
        }

        return rootNode;
    }

    /**
     * 非递归方式查找元素
     * 时间复杂度O(N) 空间复杂度O(1)
     *
     * @param rootNode
     * @param data
     * @return
     */
    public static BinarySearchTreeNode<Integer> findDataNoRecursive(BinarySearchTreeNode<Integer> rootNode, int data) {

        if (rootNode == null) {
            return null;
        }
        while (rootNode != null) {
            if (rootNode.getData() == data) {
                return rootNode;
            } else if (data > rootNode.getData()) {
                rootNode = rootNode.getRight();
            } else {
                rootNode = rootNode.getLeft();
            }
        }
        return null;
    }

    /**
     * 递归方式查找bst最小元素
     * 时间复杂度O(N) 空间复杂度O(N)
     *
     * @param rootNode
     * @return
     */
    public static BinarySearchTreeNode<Integer> findMinData(BinarySearchTreeNode<Integer> rootNode) {

        if (rootNode == null) {
            return null;
        }
        if (rootNode.getLeft() == null) {
            return rootNode;
        } else {
            return findMinData(rootNode.getLeft());
        }
    }

    /**
     * 非递归查找最小元素
     * 时间复杂度O(N) 空间复杂度O(1)
     *
     * @param rootNode
     * @return
     */
    public static BinarySearchTreeNode<Integer> findMinDataNoRecursive(BinarySearchTreeNode<Integer> rootNode) {

        if (rootNode == null) {
            return null;
        }

        while (rootNode.getLeft() != null) {
            rootNode = rootNode.getLeft();
        }
        return rootNode;
    }

    /**
     * 递归方式查找bst最大元素
     * 时间复杂度O(N) 空间复杂度O(N)
     *
     * @param rootNode
     * @return
     */
    public static BinarySearchTreeNode<Integer> findMaxData(BinarySearchTreeNode<Integer> rootNode) {

        if (rootNode == null) {
            return null;
        }
        if (rootNode.getRight() == null) {
            return rootNode;
        } else {
            return findMaxData(rootNode.getRight());
        }
    }

    /**
     * 非递归查找最大元素
     * 时间复杂度O(N) 空间复杂度O(1)
     *
     * @param rootNode
     * @return
     */
    public static BinarySearchTreeNode<Integer> findMaxDataNoRecursive(BinarySearchTreeNode<Integer> rootNode) {

        if (rootNode == null) {
            return null;
        }

        while (rootNode.getLeft() != null) {
            rootNode = rootNode.getRight();
        }
        return rootNode;
    }

    public static BinarySearchTreeNode<Integer> insertNode(BinarySearchTreeNode<Integer> rootNode, int data) {

        if (rootNode == null) {
            rootNode = new BinarySearchTreeNode<>();
            rootNode.setData(data);
            rootNode.setLeft(null);
            rootNode.setRight(null);
            return rootNode;
        } else {
            if (data < rootNode.getData()) {
                rootNode.setLeft(insertNode(rootNode.getLeft(), data));
            } else {
                rootNode.setRight(insertNode(rootNode.getRight(), data));
            }
        }
        return rootNode;
    }



}
